# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-01-21 10:40:20
# @Last Modified by:   bao
# @Last Modified time: 2017-02-17 11:14:32
#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-

'''
The demand estimation algorithm from Hedera paper is implemented here
hedera: dynamic flow scheduling for data center networks
Max-min fairness bandwidth allocation
'''

from datetime import datetime

def demand_estimation(flows_src, flows_dst):
    starttime = datetime.now()
    Host_Matrix ={}
    for src in flows_src:
        Host_Matrix[src] = {}
        for dst in flows_src[src]:
            Host_Matrix[src][dst] = {'demand': 0, 'demandInit': 0, 'converged' : False, 'FlowNmbr' : 0}
  
    for src in flows_src:
        for dst in flows_src[src]:
            Host_Matrix[src][dst]['FlowNmbr'] += 1

    demandChange = True
    while demandChange:
       demandChange = False
    
       for src in flows_src:
            Est_Src(Host_Matrix, flows_src, flows_dst, src)

       for dst in flows_dst:
            Est_Dst(Host_Matrix, flows_src, flows_dst, dst)

       for src in flows_src:
           for dst in flows_src[src]:
               if Host_Matrix[src][dst]['demandInit'] != Host_Matrix[src][dst]['demand']:
                   NoChange = True
                   Host_Matrix[src][dst]['demandInit'] = Host_Matrix[src][dst]['demand']
        
    endtime = datetime.now()
    timediff = endtime - starttime
    print 'Fariness Estimation time ',timediff
    return Host_Matrix

def Est_Src(Host_Matrix, flows_src, flows_dst, src):
    dF = 0
    nU = 0
    for dst in flows_src[src]:
        if flows_src[src][dst]['converged']:
            dF += flows_src[src][dst]['demand']
        else:
            nU += 1
    if nU != 0:
        eS = (1.0 - dF) / nU
        for dst in flows_src[src]:
            if not flows_src[src][dst]['converged']:
                Host_Matrix[src][dst]['demand'] = eS 
                flows_src[src][dst]['demand'] = eS
                flows_dst[dst][src]['demand'] = eS

def Est_Dst(Host_Matrix, flows_src, flows_dst, dst):
    dT = 0
    dS = 0
    nR = 0
    for src in flows_dst[dst]:
        flows_dst[dst][src]['recLimited'] = True
        flows_src[src][dst]['recLimited'] = True
        dT += flows_dst[dst][src]['demand']
        nR += 1
    if dT <= 1.0:
        return
    eS = 1.0 / nR

    flagFlip=True
    while flagFlip:
        flagFlip = False
        nR = 0
        for src in flows_dst[dst]:
            if flows_dst[dst][src]['recLimited']:
                if flows_dst[dst][src]['demand'] < eS:
                    dS += flows_dst[dst][src]['demand']
                    flows_dst[dst][src]['recLimited'] = False
                    flows_src[src][dst]['recLimited'] = False
                    flagFlip = True
                else:
                    nR += 1
        eS = (1.0-dS)/nR
            
    for src in flows_dst[dst]:
        if flows_dst[dst][src]['recLimited']:
            Host_Matrix[src][dst]['demand'] = eS
            Host_Matrix[src][dst]['converged'] = True
            flows_dst[dst][src]['converged'] = True
            flows_src[src][dst]['converged'] = True
            flows_dst[dst][src]['demand'] = eS
            flows_src[src][dst]['demand'] = eS

def transform (Host_Matrix, host_location, tf_graph, base_len, threshold=0.1):
    '''
    Transform the host-level traffic demand matrix to switch-level demand matrix
    @ host_location : {host_ip:(dpid,port)}
    tf_graph
    node "degree"
    edge "weight"
    '''
    starttime = datetime.now()
    for host_src in Host_Matrix:
        sw_src = host_location[host_src][0]
        for host_dst in Host_Matrix[host_src]:
            sw_dst = host_location[host_dst][0]
            if Host_Matrix[host_src][host_dst]['demand'] > threshold:
                if sw_src != sw_dst:
                    if (sw_src, sw_dst+base_len) not in tf_graph.edges():
                        tf_graph.add_edge(sw_src, sw_dst+base_len, weight = Host_Matrix[host_src][host_dst]['demand'])
                    else:
                        tf_graph.edge[sw_src][sw_dst+base_len]['weight'] += Host_Matrix[host_src][host_dst]['demand']
    endtime = datetime.now()
    timediff = endtime - starttime
    print 'Transform time ', timediff